package pers.qianyu.month_202102.date_20210218;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 337. 打家劫舍 III
 * https://leetcode-cn.com/problems/house-robber-iii/
 * - 另一种思路
 *
 * @author mizzle rain
 * @date 2021-02-18 20:08
 */
public class RobThree {
    Map<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        return dp(root);
    }

    // dp 函数的定义为：当起点为 root 的情况下，可以偷到的最大金额
    private int dp(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int doRub = root.val + (root.left == null ? 0 : dp(root.left.left) + dp(root.left.right))
                + (root.right == null ? 0 : dp(root.right.left) + dp(root.right.right));
        int undoRob = dp(root.left) + dp(root.right);
        int res = Math.max(undoRob, doRub);
        memo.put(root, res);
        return res;
    }
}
